⟸ Go Back ⟸

Exercise 3 (Homework 7).

(P, NP, coNP)

Closure properties of \mathsf{P}, \mathsf{NP} and \mathsf{coNP}

The goal of this exercise is to revise some closure properties of \mathsf{P}, \mathsf{NP}, and \mathsf{coNP}.

1. (closure w.r.t union) Prove the following implications
   1. Given A and B in \mathsf{P}, A\cup B\in \mathsf{P}.
   2. Given A and B in \mathsf{NP}, A\cup B\in \mathsf{NP}.
   3. Given A and B in \mathsf{coNP}, A\cup B\in \mathsf{coNP}.
2. (closure w.r.t intersection) Prove the following implications
   1. Given A and B in \mathsf{P}, A\cap B\in \mathsf{P}.
   2. Given A and B in \mathsf{NP}, A\cap B\in \mathsf{NP}.
   3. Given A and B in \mathsf{coNP}, A\cap B\in \mathsf{coNP}.
      
3. (closure w.r.t concatenation) Prove the following implications
   1. Given A and B in \mathsf{P}, A\cdot B\in \mathsf{P}.
   2. Given A and B in \mathsf{NP}, A\cdot B\in \mathsf{NP}.
   3. Given A and B in \mathsf{coNP}, A\cdot B\in \mathsf{coNP}.